While the addressing methodology used in the practice of the invention may be of more general application as well, it will be illustratively described herein with reference to its preferred and best mode use with output-buffered electronic switch fabrics (ESF) of the above-mentioned type, wherein a central shared memory architecture is employed, comprised of a plurality of similar successive data memory channels defining a memory space, with fixed limited times of data distribution from the input ports successively into the successive memory cells of the successive memory channels, and in striped fashion across the memory space. This enables non-blocking shared memory output-buffered data switching, with the data stored across the memory channels uniformly. By so limiting the times of storing data from an input port in each successive memory channel, as explained in said copending applications, the problem is admirably solved of guaranteeing that data is written into memory in a non-blocking fashion across the memory space and with bounded delay.
Illustrative Preferred Electronic Switch Fabric (ESF) for Use with the Invention
This preferred technique, embraces a method of receiving and outputting a plurality m of queues of data traffic streams to be switched from data traffic line card input ports to output ports. A plurality n of similar successive data memory channels is provided, each having a number of memory cells defining the shared memory space assigned to the m queues. Buffering is effected for m memory cells, disposed in front of each memory channel, to receive and buffer data switched thereto from line card traffic streams, and providing sufficient buffering to absorb a burst from up to n line cards. Successive data is distributed in each of the queues during fixed limited times only to corresponding successive cells of each of the successive memory channels and, as before stated, in striped fashion across the memory space, thereby providing the non-blocking shared memory output-buffered data switching I/O (input/output) ports. Each packet from an input port gets an address in the destination queue from an address generator, defining the location in the shared memory in which the packet will be stored. Such use of an output-buffered switch fabric enables packets destined for a queue to come from all input ports; and all these packets are written into the shared memory such that, as before mentioned, there is no overlap among packets and no holes or gaps between adjacent packets. The address of every packet, accordingly, depends upon all the packets that have been previously assigned an address, and the packets must be assigned sequentially. This parallel processing algorithm enables the address generator to be scalable for both port count and bandwidth.
As an example, the system embodying the shared memory operating with the address generating methodology of the present invention can support minimum 40 byte packets with no impact on the switch fabric performance, receiving from each 10 Gbps port, a 40 byte packet every 40 ns fixed time slot, and with capability to assign addresses for 64 packets every 40ns, as where all these packets belong to the same queue.
Illustrative Address Generator (AG) for Use with the Invention
With the use of the before-mentioned closed ring sequential address generators for the shared-memory output-buffered electronic switch fabric, the technique for addressing the sequential data packets received from a plurality of input data line cards to enable their memory storage in successive shared memory block sections of the output-buffered switch fabric, (each assigned to a queue dedicated for an output port), comprises connecting a plurality of similar subaddress generators successively in a closed ring structure, previously mentioned. Each subaddress generator is, as described in the first-named copending application, capable of assigning addresses for predetermined size data byte packets of input data traffic received in a plurality of successive time slots, to produce packet composition into so-called super packets that are ordered based on time of arrival. A continuous memory block is allocated for a super packet by assigning an initial super packet address in the destination queue from a subaddress generator, and thereupon generating the starting address of the next super packet by adding the super packet size to said initial starting address and moving to the next subaddress generator sequentially along the successive subaddress generators of the ring. This sequentially allocates memory in the shared memory sections from subaddress generator to subaddress generator along the ring. Upon the assigning of an address to each super packet, packet decomposition is produced at the corresponding subaddress generator by simultaneously assigning addresses for the individual packets in the super packet, based on their arrival order. All subaddress generators are operated to execute their respective said packet composition and packet decomposition concurrently, and the packets are written into the shared memory sections such that there is no overlap among the packets and no holes between adjacent packets, with said memory allocating moving to the next subaddress generator after an allocation time period of more than one time slot, and with said time period being proportional to the maximum size of a super packet. To support 640 Gbps input bandwidth with 40-byte packets, for example, the AG sub-system has to be capable of generating an address in 0.5 ns.
The Error Protection and Correction Redundancy Concept of the Present Invention
Illustrating the invention herein as exemplary applied to the above preferred shared-memory and output-buffered ESF and AG ring structure, it should be observed that the switch fabric is a highly distributed architecture comprised of several devices that play varying degrees of role as data path and control path elements. The AG, indeed, is the only centralized element in the ESF that primarily manages the control path via parallel computations to achieve the required bandwidth needed for writing data into the ESF shared memory element, as later detailed.
With the multiple AG units connected in a ring topology to scale-up the performance of the ESF, AGs in practice are co-located on a single board and pragmatically placed on a bandwidth management processor (BMP) card. Any error on the AG ring, however, can fester unhindered and cause serious problems with the ESF, leading to unreliable data that egresses one or more line cards. Without an automatic error recovery solution, system software will have to intervene and correct the problem by resetting in part or whole, the entire AG ring. Considering the number of high-speed feeds into the ESF, this can lead to loss of a significant quantity of data.
It is to the solution of such problems that the present invention is accordingly directed, providing a novel multiple AG ring redundancy system that allows the ESF automatically to correct the AG ring in face of errors on a per queue or on multiple AG level.
Objects of Invention
An object of the present invention, therefore, is to provide a new and improved method of and apparatus for protecting and correcting errors in data packet flow in closed ring address generators of the type particularly, though not exclusively, suited to enable packet addressing in an output-buffered shared memory ESF, and the like.
A further object is to provide a novel address generator redundancy system for carrying out the method of the addressing technique of the invention error-free, and embodying a pair of duplicate AG ring structures each of successively connected subaddress generators, with memory allocation of dataflow effected sequentially from subaddress generator to subaddress generator along the each ring path, and with the rings linked for increasing the reliability of the ESF, with each ring protecting the other from possible errors within each link.
Still another object is to provide such duplicate parallel data flow paths, linked to enable synchronization thereof, and with substitution and restoration of a correct data packet in one path for a corresponding erroneous packet in the other path, “on-the-fly”, and which is of more generic use for real-time data error correction in parallel structures of data flow paths generically, other than ring structures.
Other and further objects will be explained hereinafter and are more particularly detailed in the accompanying claims.